剑指Offer 17 合并两个排序的链表

题目描述

输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

思路

两个链表，每次对比头指针，谁小就拿走，然后next补充为头指针；挨个比较；

代码

public ListNode Merge(ListNode list1,ListNode list2) {
           if (list1==null)
           return list2;
      else if (list2==null)
           return list1;
       ListNode node = null;
       if (list1.val<list2.val)
       {
           node=list1;
           node.next= Merge(list1.next,list2);
       }
       else
       {
           node=list2;
           node.next = Merge(list1,list2.next);
       }
       return node;
   }

收获

1. 递归中最好使用中间变量，像上面的head最好不要改变，这样比较简单，而且中间变量用于返回值，这样不影响递归；